from kiwi.core.base import Instances, Instance 
from kiwi.numalgo.nonmetric import *
from kiwi.learner.learner import Classifier

#*****************************************************************************
# PURPOSE: 
# USAGE:   
# PASSED ARGS:  
# RETURN ARGS: 
# Error - Fail Error Message
#*****************************************************************************
def CreateTestSet():
	newInstances = Instances(["A","B","C"])
	newInstances.setTargetIndex()
	
	dataset = [ [ 1, 1, 'yes'],
				[ 1, 1, 'yes'],
				[ 1, 0, 'no' ],
				[ 0, 1, 'no' ],
				[ 0, 1, 'no' ] ]
	for dataline in dataset:
		newInstances.addInstance( dataline )
	labels = [ 'no surfacing','flippers']	
	return newInstances,labels


#*************************************************************************
# PURPOSE: 
# USAGE:   
# PASSED ARGS:  
# RETURN ARGS: 
# Error - Fail Error Message
#*************************************************************************	
def SplitDataset( instances, pos, target ):
	if instances is None:
		return None
	cols = instances.cols()
	if pos >= cols:
		return None
	newInstances = instances.emptySet( [ pos ], reverse = True )
	newInstances.setTargetIndex()		
	for instance in instances:
		if instance[ pos ] == target:
			newInstances.addInstance( instance.subline([ pos], reverse = True ))
	return 	newInstances


#*************************************************************************
# PURPOSE: 
# USAGE:   
# PASSED ARGS:  
# RETURN ARGS: 
# Error - Fail Error Message
#*************************************************************************	
def ChooseBestFeatureToSplit( instances, calImpurity = CalcShannonEntropy ):
	if not instances.hasTargetIndex() or instances.size() == 0:		
		return None		
	featureIndex = instances.getNonTargetIndex()
	if not featureIndex:
		return None
	baseImpurity = calImpurity( instances )
	bestInfoGain = 0.0
	bestFeature = None
	for i in featureIndex:
		featurevalue =  [ instance[ i ] for instance in instances ]
		uniqVals = set( featurevalue )
		newImpurity = 0.0			
		for value in uniqVals:
			subset = SplitDataset( instances, i, value )
			prob = subset.size( ) / instances.size( )
			newImpurity += prob * calImpurity( subset )
		infoGain = baseImpurity - newImpurity
		
		if( infoGain > bestInfoGain ):
			bestInfoGain = infoGain
			bestFeature = i

	return 	bestFeature


#*************************************************************************
# PURPOSE: 
# USAGE:   
# PASSED ARGS:  
# RETURN ARGS: 
# Error - Fail Error Message
#*************************************************************************	
def CreateTree( instances, labels, calImpurity = CalcShannonEntropy ):
	labels = labels[:]	
	# Stop when all classes are equal
	targetList = instances.getTargetValues()
	if targetList.count( targetList[ 0 ] ) == len( targetList ) :
		return targetList[ 0 ]
	
	# Stop when no more attribute left
	if instances.cols() == 1:
		majorityClass = MajorityCnt( instances )
		return  majorityClass[ 0 ][ 0 ]

	# Select best feature for split
	bestfeature = ChooseBestFeatureToSplit( instances, calImpurity )
	
	# Label current node		
	bestlabel = labels[ bestfeature ]						
	myTree = { bestlabel: { }  }
	del labels[ bestfeature ]

	# Split dataset and create subtrees
	uniqValues = set( [ instance[ bestfeature ] for instance in instances ] )
	for value in uniqValues:
		newInstances = SplitDataset(instances,bestfeature, value )
		subLabels = labels[:]
		myTree[ bestlabel ][ value ] = CreateTree( newInstances, subLabels )		
	return myTree

#*************************************************************************
# PURPOSE: 
# USAGE:   
# PASSED ARGS:  
# RETURN ARGS: 
# Error - Fail Error Message
#*************************************************************************	
def LabelInstance( inputTree, featLabels, instance ):
	splitStr = inputTree.keys()[ 0 ]
	splitValues = inputTree[ splitStr ]
	featIndex = featLabels.index( splitStr )
	
	# Search data block after split	
	for value in splitValues.keys():
		if instance[ featIndex ] == value:
			# Still has subtree
			if type( splitValues[ value ] ).__name__ == 'dict':
				classLabel = LabelInstance( splitValues[ value ],featLabels, instance   )
			else:# leaf
				classLabel = splitValues[ value ]
	return classLabel
#*************************************************************************
# PURPOSE: 
# USAGE:   
# PASSED ARGS:  
# RETURN ARGS: 
# Error - Fail Error Message
#*************************************************************************
def GetNumLeafs( tree ):
	pass


#*************************************************************************
# PURPOSE: 
# USAGE:   
# PASSED ARGS:  
# RETURN ARGS: 
# Error - Fail Error Message
#*************************************************************************
def GetTreeDepth( tree ):
	pass





#*****************************************************************************
# PURPOSE: 
# USAGE:   
# PASSED ARGS:  
# RETURN ARGS: 
# Error - Fail Error Message
#*****************************************************************************
class BaseTree( Classifier ):	
	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************
	def __init__( self , name = "BaseTree", type = "Tree" ):
		Classifier.__init__(self, name, type  )
		self.setParam("IMPURITYCALC", CalcShannonEntropy )

	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************		
	def setImpurityMethod( self , method = CalcShannonEntropy ):
		self.setParam("IMPURITYCALC", method )

	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************
	def getImpurityMethod( self ):
		return 	self.getParam("IMPURITYCALC")


	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************	
	def setStopThreshold( self, value ):
		self.setParam("STOPTHRESHOLD", value )
	
	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************
	def getStopThreshold( self):
		return self.getParam("STOPTHRESHOLD")

	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************
	def setLabels( self, labels ):
		self.setParam("LABELS", labels )

	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************
	def getLabels( self ):
		self.getParam("LABELS")

	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************	
	def setTree( self, tree ): 
		self.setParam("TREE", tree )

	#*************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*************************************************************************
	def getTree( self ):
		return self.getParam("TREE")

	#*****************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*****************************************************************************	
	def buildClassifier( self,  instances  ):
		labels = self.getParam("LABELS")
		impurityFunc = self.getParam("IMPURITYCALC")
		resultTree = CreateTree( instances, labels, impurityFunc  )
		if resultTree:
			self.setTree( resultTree )
		return resultTree

	#*****************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*****************************************************************************
	def classifyInstance( self, instance ):
		inputTree = self.getParam("TREE")		
		labels = self.getParam("LABELS")
		return LabelInstance( inputTree, labels, instance  )

	#*****************************************************************************
	# PURPOSE: 
	# USAGE:   
	# PASSED ARGS:  
	# RETURN ARGS: 
	# Error - Fail Error Message
	#*****************************************************************************
	def showTree( self ):
		pass

